package top.minuy.subject.leetcode.recursive;

import top.minuy.structure.linear.array.Array;
/**
 * @author Minuy
 * @time 20:28
 * @date 2021/8/24
 */
public class Sum {

    static class time_sta {
        public double e1;
        public double e2;
    }

    public static int sum_(int[] arr) {
        int sum = 0;
        for (int c : arr) {
            sum += c;
        }
        return sum;
    }

    public static int sum(int[] arr) {
        return sum(arr, 0);
    }

    private static int sum(int[] arr, int l) {
        if (l == arr.length - 1) {
            return arr[l];
        }
        return arr[l] + sum(arr, l + 1);
    }

    public static void main(String[] args) {
        Array<time_sta> at = new Array<>();
        int opCount = 10000;
        boolean success = true;
        while (success) {
            try {
                time_sta ts = test(opCount);
                at.addLast(ts);
                success = true;
            } catch (java.lang.StackOverflowError e) {
                success = false;
                System.out.println();
                System.out.println("opCount = " + opCount);
                System.out.println("出错，栈溢出。");
            }
            opCount += 1;
        }

        double e1_avg = 0;
        double e2_avg = 0;

        for (int i = 0; i < at.getSize(); i++) {
            e1_avg += at.get(i).e1;
            e2_avg += at.get(i).e2;
        }

        e1_avg /= at.getSize();
        e2_avg /= at.getSize();

        System.out.println(String.format("递归 : time = %f s, 循环 : time = %f s", e1_avg, e2_avg));
    }

    public static time_sta test(int opCount) {
        time_sta ts = new time_sta();
        int sumVal;

        int[] arr = new int[opCount];
        for (int i = 0; i < opCount; i++) {
            arr[i] = opCount;
        }

        long startTime = System.nanoTime();
        sumVal = sum(arr);
        long endTime = System.nanoTime();
        System.out.println("递归：" + sumVal);

        ts.e1 = (endTime - startTime) / 1000000000.0;

        System.out.println("time = " + ts.e1 + " s");

        startTime = System.nanoTime();
        sumVal = sum_(arr);
        endTime = System.nanoTime();
        System.out.println("循环：" + sumVal);

        ts.e2 = (endTime - startTime) / 1000000000.0;

        System.out.println("time = " + ts.e2 + " s");

        return ts;
    }
}
